import random
import time

class TestDataGenerator:
    """测试数据生成器"""
    
    @staticmethod
    def get_basic_cases():
        """基础测试用例"""
        return [
            ([["1","0","1","0","0"],
              ["1","0","1","1","1"],
              ["1","1","1","1","1"],
              ["1","0","0","1","0"]], 4, "示例1"),
            ([["0","1"], ["1","0"]], 1, "示例2"),
            ([["0"]], 0, "单个0"),
            ([["1"]], 1, "单个1"),
            ([], 0, "空矩阵"),
            ([["1","1"], ["1","1"]], 4, "2x2全1"),
        ]
    
    @staticmethod
    def get_special_cases():
        """特殊测试用例"""
        return [
            ([["0"]*3 for _ in range(3)], 0, "3x3全0"),
            ([["1"]*3 for _ in range(3)], 9, "3x3全1"),
            ([["1","1","0"], ["1","1","0"], ["0","0","0"]], 4, "L形状"),
        ]
    
    @staticmethod
    def generate_random(rows, cols, density=0.5):
        """生成随机矩阵"""
        return [['1' if random.random() < density else '0' 
                for _ in range(cols)] for _ in range(rows)]


class TestRunner:
    """测试运行器"""
    
    def __init__(self, solution_class):
        self.solution = solution_class()
        self.generator = TestDataGenerator()
        self.passed = 0
        self.total = 0
    
    def run_test(self, matrix, expected, desc):
        """运行单个测试"""
        self.total += 1
        
        start_time = time.time()
        result = self.solution.maximalSquare(matrix)
        end_time = time.time()
        
        status = "PASS" if result == expected else "FAIL"
        if status == "PASS":
            self.passed += 1
        
        print(f"测试 {self.total}: {desc}")
        print(f"  结果: {result} | 期望: {expected} | {status}")
        print(f"  耗时: {(end_time - start_time)*1000:.2f}ms")
        print("-" * 30)
    
    def run_all_tests(self):
        """运行所有测试"""
        print("最大正方形测试")
        print("=" * 30)
        
        # 基础测试
        print("基础测试:")
        for matrix, expected, desc in self.generator.get_basic_cases():
            self.run_test(matrix, expected, desc)
        
        # 特殊测试
        print("\n特殊测试:")
        for matrix, expected, desc in self.generator.get_special_cases():
            self.run_test(matrix, expected, desc)
        
        # 随机测试
        print("\n随机测试:")
        for size in [5, 10]:
            matrix = self.generator.generate_random(size, size, 0.5)
            result = self.solution.maximalSquare(matrix)
            self.run_test(matrix, result, f"{size}x{size}随机")
        
        # 总结
        print("=" * 30)
        print(f"测试完成: {self.passed}/{self.total} 通过")
        print(f"通过率: {self.passed/self.total*100:.1f}%")


# Solution类
class Solution(object):
    def maximalSquare(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        max_side = 0
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    max_side = max(max_side, dp[i][j])
        
        return max_side * max_side


if __name__ == "__main__":
    runner = TestRunner(Solution)
    runner.run_all_tests()
